#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    Node* connect(Node* root)
    {
        if (root == nullptr)
            return nullptr;
        queue<Node*> q;
        q.push(root);
        while (!q.empty())
        {
            int len = q.size();
            for (int i = 0; i < len; ++i)
            {
                Node* cur = q.front();
                q.pop();
                if (i < len - 1)
                {
                    cur->next = q.front();
                }
                if (cur->left != nullptr)
                    q.push(cur->left);
                if (cur->right != nullptr)
                    q.push(cur->right);
            }
        }
        return root;
    }
};

class Solution {
public:
    Node* connect(Node* root)
    {
        if (root == nullptr)
            return root;
        Node* leftNode = root;
        while (leftNode->left != nullptr)
        {
            Node* head = leftNode;
            while (head != nullptr)
            {
                head->left->next = head->right;
                if (head->next != nullptr)
                    head->right->next = head->next->left;
                head = head->next;
            }
            leftNode = leftNode->left;
        }
        return root;
    }
};

